{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Total Beauty of the Gardens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumBeauty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #花园的最大总美丽值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 是&nbsp;<code>n</code>&nbsp;个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始大小为 <code>n</code>&nbsp;的整数数组&nbsp;<code>flowers</code>&nbsp;，其中&nbsp;<code>flowers[i]</code>&nbsp;是第 <code>i</code>&nbsp;个花园里已经种的花的数目。已经种了的花 <strong>不能</strong>&nbsp;移走。同时给你&nbsp;<code>newFlowers</code>&nbsp;，表示 Alice 额外可以种花的&nbsp;<strong>最大数目</strong>&nbsp;。同时给你的还有整数&nbsp;<code>target</code>&nbsp;，<code>full</code>&nbsp;和&nbsp;<code>partial</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果一个花园有 <strong>至少</strong>&nbsp;<code>target</code>&nbsp;朵花，那么这个花园称为 <strong>完善的</strong>&nbsp;，花园的 <strong>总美丽值</strong>&nbsp;为以下分数之 <strong>和</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><b>完善</b> 花园数目乘以&nbsp;<code>full</code>.</li>\n",
    "\t<li>剩余 <strong>不完善</strong>&nbsp;花园里，花的 <strong>最少数目</strong>&nbsp;乘以&nbsp;<code>partial</code>&nbsp;。如果没有不完善花园，那么这一部分的值为&nbsp;<code>0</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 Alice 种最多 <code>newFlowers</code>&nbsp;朵花以后，能得到的<strong>&nbsp;最大</strong>&nbsp;总美丽值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1\n",
    "<b>输出：</b>14\n",
    "<b>解释：</b>Alice 可以按以下方案种花\n",
    "- 在第 0 个花园种 2 朵花\n",
    "- 在第 1 个花园种 3 朵花\n",
    "- 在第 2 个花园种 1 朵花\n",
    "- 在第 3 个花园种 1 朵花\n",
    "花园里花的数目为 [3,6,2,2] 。总共种了 2 + 3 + 1 + 1 = 7 朵花。\n",
    "只有 1 个花园是完善的。\n",
    "不完善花园里花的最少数目是 2 。\n",
    "所以总美丽值为 1 * 12 + 2 * 1 = 12 + 2 = 14 。\n",
    "没有其他方案可以让花园总美丽值超过 14 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6\n",
    "<b>输出：</b>30\n",
    "<b>解释：</b>Alice 可以按以下方案种花\n",
    "- 在第 0 个花园种 3 朵花\n",
    "- 在第 1 个花园种 0 朵花\n",
    "- 在第 2 个花园种 0 朵花\n",
    "- 在第 3 个花园种 2 朵花\n",
    "花园里花的数目为 [5,4,5,5] 。总共种了 3 + 0 + 0 + 2 = 5 朵花。\n",
    "有 3 个花园是完善的。\n",
    "不完善花园里花的最少数目为 4 。\n",
    "所以总美丽值为 3 * 2 + 4 * 6 = 6 + 24 = 30 。\n",
    "没有其他方案可以让花园总美丽值超过 30 。\n",
    "注意，Alice可以让所有花园都变成完善的，但这样她的总美丽值反而更小。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= flowers.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= flowers[i], target &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= newFlowers &lt;= 10<sup>10</sup></code></li>\n",
    "\t<li><code>1 &lt;= full, partial &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-total-beauty-of-the-gardens](https://leetcode.cn/problems/maximum-total-beauty-of-the-gardens/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-total-beauty-of-the-gardens](https://leetcode.cn/problems/maximum-total-beauty-of-the-gardens/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,1,1]\\n7\\n6\\n12\\n1', '[2,4,5,3]\\n10\\n5\\n2\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n=len(flowers)\n",
    "        if flowers[0]>=target:\n",
    "            return n*full\n",
    "        leftFlowers=newFlowers-target*n\n",
    "        for i in range(n):\n",
    "            flowers[i]=min(flowers[i],target)\n",
    "            leftFlowers+=flowers[i]\n",
    "\n",
    "        ans,x,sumFlowers=0,0,0\n",
    "        for i in range(n+1):\n",
    "            if leftFlowers>=0:\n",
    "                while x<i and flowers[x]*x-sumFlowers<=leftFlowers:\n",
    "                    sumFlowers += flowers[x]\n",
    "                    x+=1\n",
    "                beauty=(n-i)*full\n",
    "                if x:\n",
    "                    beauty +=min((leftFlowers+sumFlowers)//x,target-1)*partial\n",
    "                ans=max(ans,beauty)\n",
    "            if i<n:\n",
    "                leftFlowers += target-flowers[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        #暴力的解法怎么做，也没想到\n",
    "        flowers.sort()\n",
    "        n=len(flowers)\n",
    "        if flowers[0]>=target:return n*full\n",
    "        left=newFlowers-target*n #这里是个负数吧\n",
    "        for i in range(n):\n",
    "            flowers[i]=min(flowers[i],target)\n",
    "            left+=flowers[i]\n",
    "        ans,x,sumflowers=0,0,0\n",
    "        for i in range(1+n):\n",
    "            if left>=0:\n",
    "                while x<i and flowers[x]*x-sumflowers<=left:\n",
    "                    sumflowers+=flowers[x]\n",
    "                    x+=1\n",
    "                beauty=(n-i)*full\n",
    "                if x:\n",
    "                    beauty+=min((left+sumflowers)//x,target-1)*partial\n",
    "                ans=max(ans,beauty)\n",
    "            if i<n:left+=target-flowers[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\r\n",
    "        flowers.sort()\r\n",
    "        n = len(flowers)\r\n",
    "        if flowers[0] >= target:  # 剪枝，此时所有花园都是完善的\r\n",
    "            return n * full\r\n",
    "\r\n",
    "        leftFlowers = newFlowers - target * n  # 填充后缀后，剩余可以种植的花\r\n",
    "        for i in range(n):\r\n",
    "            flowers[i] = min(flowers[i], target)  # 去掉多余的花\r\n",
    "            leftFlowers += flowers[i]  # 补上已有的花\r\n",
    "\r\n",
    "        ans, x, sumFlowers = 0, 0, 0\r\n",
    "        for i in range(n + 1):  # 枚举后缀长度 n-i\r\n",
    "            if leftFlowers >= 0:\r\n",
    "                # 计算最长前缀的长度\r\n",
    "                while x < i and flowers[x] * x - sumFlowers <= leftFlowers:\r\n",
    "                    sumFlowers += flowers[x]\r\n",
    "                    x += 1  # 注意 x 只增不减，二重循环的时间复杂度为 O(n)\r\n",
    "                beauty = (n - i) * full  # 计算总美丽值\r\n",
    "                if x:\r\n",
    "                    beauty += min((leftFlowers + sumFlowers) // x, target - 1) * partial\r\n",
    "                ans = max(ans, beauty)\r\n",
    "            if i < n:\r\n",
    "                leftFlowers += target - flowers[i]\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        if flowers[0] >= target:  # 剪枝，此时所有花园都是完善的\n",
    "            return n * full\n",
    "\n",
    "        leftFlowers = newFlowers - target * n  # 填充后缀后，剩余可以种植的花\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(flowers[i], target)  # 去掉多余的花\n",
    "            leftFlowers += flowers[i]  # 补上已有的花\n",
    "\n",
    "        ans, x, sumFlowers = 0, 0, 0\n",
    "        for i in range(n + 1):  # 枚举后缀长度 n-i\n",
    "            if leftFlowers >= 0:\n",
    "                # 计算最长前缀的长度\n",
    "                while x < i and flowers[x] * x - sumFlowers <= leftFlowers:\n",
    "                    sumFlowers += flowers[x]\n",
    "                    x += 1  # 注意 x 只增不减，二重循环的时间复杂度为 O(n)\n",
    "                beauty = (n - i) * full  # 计算总美丽值\n",
    "                if x:\n",
    "                    beauty += min((leftFlowers + sumFlowers) // x, target - 1) * partial\n",
    "                ans = max(ans, beauty)\n",
    "            if i < n:\n",
    "                leftFlowers += target - flowers[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        \n",
    "        # 剪枝，此时所有花园都是完善的\n",
    "        if flowers[0] >= target:\n",
    "            return n * full\n",
    "\n",
    "        leftFlowers = newFlowers - target * n  # 填充后缀后，剩余可以种植的花\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(flowers[i], target)  # 去掉多余的花\n",
    "            leftFlowers += flowers[i]  # 补上已有的花\n",
    "\n",
    "        ans, x, sumFlowers = 0, 0, 0\n",
    "        for i in range(n + 1):  # 枚举后缀长度 n-i\n",
    "            if leftFlowers >= 0:\n",
    "                # 计算最长前缀的长度\n",
    "                while x < i and flowers[x] * x - sumFlowers <= leftFlowers:\n",
    "                    sumFlowers += flowers[x]\n",
    "                    x += 1  # 注意 x 只增不减，二重循环的时间复杂度为 O(n)\n",
    "                \n",
    "                beauty = (n - i) * full  # 计算总美丽值\n",
    "                if x:\n",
    "                    beauty += min((leftFlowers + sumFlowers) // x, target - 1) * partial\n",
    "                ans = max(ans, beauty)\n",
    "            \n",
    "            if i < n:\n",
    "                leftFlowers += target - flowers[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n=len(flowers)\n",
    "        if flowers[0]>=target:\n",
    "            return n*full\n",
    "        leftFlowers=newFlowers-target*n\n",
    "        for i in range(n):\n",
    "            flowers[i]=min(flowers[i],target)\n",
    "            leftFlowers+=flowers[i]\n",
    "\n",
    "        ans,x,sumFlowers=0,0,0\n",
    "        for i in range(n+1):\n",
    "            if leftFlowers>=0:\n",
    "                while x<i and flowers[x]*x-sumFlowers<=leftFlowers:\n",
    "                    sumFlowers += flowers[x]\n",
    "                    x+=1\n",
    "                beauty=(n-i)*full\n",
    "                if x:\n",
    "                    beauty +=min((leftFlowers+sumFlowers)//x,target-1)*partial\n",
    "                ans=max(ans,beauty)\n",
    "            if i<n:\n",
    "                leftFlowers += target-flowers[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        if flowers[0] >= target:  # 剪枝，此时所有花园都是完善的\n",
    "            return n * full\n",
    "\n",
    "        leftFlowers = newFlowers - target * n  # 填充后缀后，剩余可以种植的花\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(flowers[i], target)  # 去掉多余的花\n",
    "            leftFlowers += flowers[i]  # 补上已有的花\n",
    "\n",
    "        ans, x, sumFlowers = 0, 0, 0\n",
    "        for i in range(n + 1):  # 枚举后缀长度 n-i\n",
    "            if leftFlowers >= 0:\n",
    "                # 计算最长前缀的长度\n",
    "                while x < i and flowers[x] * x - sumFlowers <= leftFlowers:\n",
    "                    sumFlowers += flowers[x]\n",
    "                    x += 1  # 注意 x 只增不减，二重循环的时间复杂度为 O(n)\n",
    "                beauty = (n - i) * full  # 计算总美丽值\n",
    "                if x:\n",
    "                    beauty += min((leftFlowers + sumFlowers) // x, target - 1) * partial\n",
    "                ans = max(ans, beauty)\n",
    "            if i < n:\n",
    "                leftFlowers += target - flowers[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        total=0\n",
    "        for i in range(len(flowers)):\n",
    "            flowers[i]=min(flowers[i], target)\n",
    "            total+=flowers[i]\n",
    "        flowers.sort(reverse=True)\n",
    "        n=len(flowers)\n",
    "        if flowers[n-1]>=target:\n",
    "            return full*n\n",
    "        ans=0\n",
    "        if target*n-total<=newFlowers:\n",
    "            ans=n*full\n",
    "        pre,ptr=0,0\n",
    "        for i in range(n):\n",
    "            if i!=0:\n",
    "                pre+=flowers[i-1]\n",
    "            rest=newFlowers-(target*i-pre)\n",
    "            if flowers[i]==target:\n",
    "                continue\n",
    "            if rest<0:\n",
    "                break\n",
    "            while not (ptr>=i and flowers[ptr]*(n-ptr)-total<=rest):\n",
    "                total-=flowers[ptr] #相当于后缀和\n",
    "                ptr+=1\n",
    "            rest=rest-(flowers[ptr]*(n-ptr)-total)\n",
    "            ans=max(ans, full*i+partial*min(flowers[ptr]+(rest)//(n-ptr), target-1))\n",
    "        #print(flowers)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        if flowers[0] >= target:  \n",
    "            return n * full\n",
    "\n",
    "        leftFlowers = newFlowers - target * n  # 填充后缀后，剩余可以种植的花\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(flowers[i], target)  # 去掉多余的花\n",
    "            leftFlowers += flowers[i]  # 补上已有的花\n",
    "\n",
    "        ans, x, sumFlowers = 0, 0, 0\n",
    "        for i in range(n + 1):  # 枚举后缀长度 n-i\n",
    "            if leftFlowers >= 0:\n",
    "                # 计算最长前缀的长度\n",
    "                while x < i and flowers[x] * x - sumFlowers <= leftFlowers:\n",
    "                    sumFlowers += flowers[x]\n",
    "                    x += 1  # 注意 x 只增不减，二重循环的时间复杂度为 O(n)\n",
    "                beauty = (n - i) * full  # 计算总美丽值\n",
    "                if x:\n",
    "                    beauty += min((leftFlowers + sumFlowers) // x, target - 1) * partial\n",
    "                ans = max(ans, beauty)\n",
    "            if i < n:\n",
    "                leftFlowers += target - flowers[i]\n",
    "    \n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "        # def beauty(flo):\n",
    "        #     full_cnt = 0\n",
    "        #     partial_min = target\n",
    "        #     for i in range(n):\n",
    "        #         if flo[i] >= target:\n",
    "        #             full_cnt += 1\n",
    "        #         else:\n",
    "        #             partial_min = min(partial_min, flo[i])\n",
    "        #     if partial_min == target:\n",
    "        #         partial_min = 0\n",
    "        #     return full_cnt * full +  partial_min * partial\n",
    "\n",
    "        # res = []\n",
    "        # def plant(flo, nf, k):\n",
    "        #     if k >= n or nf == 0:\n",
    "        #         res.append(beauty(flo))\n",
    "        #         return\n",
    "        #     if flo[k] >= target:\n",
    "        #         plant(flo[:], nf, k + 1)\n",
    "        #     else:\n",
    "        #         plant(flo[:], nf, k + 1)\n",
    "        #         while flo[k] <= target and nf > 0:\n",
    "        #             flo[k] += 1\n",
    "        #             nf -= 1\n",
    "        #             plant(flo[:], nf, k + 1)\n",
    "        \n",
    "        # plant(flowers, newFlowers, 0)\n",
    "        # return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort(reverse=True)\n",
    "        n = len(flowers)\n",
    "        res = 0\n",
    "        i = -1\n",
    "        while i + 1 < n and flowers[i+1] >= target:\n",
    "            i += 1 \n",
    "        j = i + 1 \n",
    "        first = 0 \n",
    "        second = sum(flowers[j:])\n",
    "        #print(flowers)\n",
    "        while i < n:\n",
    "            if j == i:\n",
    "                second -= flowers[j]\n",
    "                j += 1\n",
    "            if i >= 0:\n",
    "                first += max(target - flowers[i], 0)\n",
    "            rest = newFlowers - first \n",
    "            if rest < 0:\n",
    "                break \n",
    "            if j < n:\n",
    "                while rest + second < flowers[j] * (n-j):\n",
    "                    #print(i, j, rest, second, flowers[j], n-j)\n",
    "                    second -= flowers[j]\n",
    "                    j += 1\n",
    "                    assert j < n\n",
    "                rest_ = rest + second - flowers[j] * (n-j)\n",
    "                rmax = min(flowers[j] + (rest_) // (n-j), target-1)\n",
    "            else:\n",
    "                rmax = 0\n",
    "            res = max(res, (i+1)*full+rmax*partial)\n",
    "            #print(i, j, (i+1)*full, rmax*partial)\n",
    "            i += 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, fs: List[int], n: int, t: int, f: int, p: int) -> int:\n",
    "        def check(m,n):\n",
    "            l,r=0,m\n",
    "            while l<r:\n",
    "                mid=l+r+1>>1\n",
    "                if pre[mid]+n>=fs[mid]*(mid+1):\n",
    "                    l=mid\n",
    "                else:\n",
    "                    r=mid-1\n",
    "            return l\n",
    "        # 首先，将花园花朵按从小到大顺序排序，并计算前缀和\n",
    "        fs.sort()\n",
    "        m=len(fs)\n",
    "        cnt=0\n",
    "        if fs[0]>=t:return m*f\n",
    "        while fs[-1]>=t:\n",
    "        # 由于已经完善的花园，没得选择，只能乘以full，所以将完善的花园pop掉，数量为cnt，仅仅计算未完善的，同时更新m\n",
    "            fs.pop();m-=1;cnt+=1\n",
    "        pre=list(accumulate(fs))\n",
    "        res=0\n",
    "        if pre[-1]+n>=m*t:res=(m+cnt)*f\n",
    "        for i in range(m-1,-1,-1):\n",
    "            j=check(i,n)\n",
    "            minv=min((n+pre[j])//(j+1),t-1)\n",
    "        # 从大到小遍历flowers数组，前面已经完善过的花园数目为cnt+m-i+1，后面计算前缀和与剩余花朵之和能构造出的最大不完善花朵数，即minv=min((n+pre[j])//(j+1),t-1)，美丽值即为(cnt+m-i-1)*f+minv*p\n",
    "            res=max(res,(cnt+m-i-1)*f+minv*p)\n",
    "            if fs[i]+n>=t:\n",
    "                n-=t-fs[i]\n",
    "            else:break\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        \n",
    "        def check(m, n):\n",
    "            l, r = 0, m\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if pre[mid] + n >= flowers[mid]*(mid+1):\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid-1\n",
    "            return l\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        if flowers[0] >= target:  # all gardens are perfect\n",
    "            return n*full\n",
    "        cnt = 0  # the number of perfect graden\n",
    "        while flowers[-1] >= target:\n",
    "            flowers.pop()\n",
    "            n -= 1\n",
    "            cnt += 1\n",
    "            \n",
    "        pre = [flowers[0]]\n",
    "        for i in range(1, n):\n",
    "            pre.append(flowers[i] + pre[-1])\n",
    "        \n",
    "        ans = 0\n",
    "        if pre[-1] + newFlowers >= n * target:\n",
    "            ans = (n + cnt) * full\n",
    "    \n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            k = check(i, newFlowers)\n",
    "            min_v = min(target-1, (newFlowers+pre[k])//(k+1))\n",
    "            ans = max(ans, (cnt + n - i - 1)*full + min_v*partial)\n",
    "            if flowers[i] + newFlowers >= target:\n",
    "                newFlowers -= target - flowers[i]\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:        \n",
    "        # 第一步 预处理 先处理完善的\n",
    "        q = [x for x in flowers if x < target]\n",
    "        m, n = len(flowers), len(q)\n",
    "        res = (m - n) * full\n",
    "        if not q: return res\n",
    "        if (n*target) <= (newFlowers+sum(q)):\n",
    "            return res+(n-1)*full+max(full,(target-1)*partial)\n",
    "        # 第二步 排序 需求前缀和\n",
    "        #ans=0\n",
    "        q.sort(reverse=True)\n",
    "        acc = list(accumulate(q, initial=0))\n",
    "        #need = list(accumulate([target - x for x in q], initial=0))\n",
    "\n",
    "        # 第三步 枚举「完善」和「不完善」的分界线\n",
    "        # 如果能全部完善，先按全完善计算\n",
    "        ans = 0 # full * n if (n*target) <= (newFlowers+sum(q)) else 0\n",
    "        #ans = full * n if need[n] <= newFlowers else 0\n",
    "\n",
    "        j = 0 \n",
    "        rest=newFlowers\n",
    "        for i in range(n): # 完善 i 个\n",
    "            if i>0:  \n",
    "                rest -= target-q[i-1]\n",
    "            if rest < 0: break\n",
    "            # 确定补齐的个数 n - j 随着 i 增加，j 在原来的基础上增加\n",
    "            while i>j or (x := q[j] * (n - j) - acc[n] + acc[j]) > rest:\n",
    "                j += 1\n",
    "            \n",
    "            x = rest-x\n",
    "            x = min(target - 1, q[j] + x // (n - j)) # q[j] + 剩余平均\n",
    "            ans = max(ans, full * i + partial * x)\n",
    "\n",
    "        return res + ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        cnt_full = len(flowers) - (n := bisect_left(flowers, target))\n",
    "        if n == 0: return cnt_full * full\n",
    "        total, cur = sum(flowers[:n]), 0\n",
    "        res, need, ti = 0, [], -1\n",
    "        for i in range(n + 1):\n",
    "            if target * (n - i) - (total - cur) <= newFlowers:\n",
    "                tr = (n - i) * full\n",
    "                f_cnt = min(newFlowers - (target * (n - i) - (total - cur)), i * (target - 1) - cur)\n",
    "                while ti + 1 < len(need) and need[ti + 1] <= f_cnt:\n",
    "                    ti += 1\n",
    "                if ti != -1:\n",
    "                    tr += (flowers[ti] + (f_cnt - need[ti]) // (ti + 1)) * partial\n",
    "                if res < tr: res = tr\n",
    "            if i < n:\n",
    "                need.append(i * flowers[i] - cur)\n",
    "                cur += flowers[i]\n",
    "        return cnt_full * full + res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        # s = 完善园数目 * full +  min(剩余不完善 花园里花的最少数目, 0) * partial\n",
    "        # 模拟就完事了\n",
    "  \n",
    "        n1 = 0\n",
    "        n2 = 0\n",
    "        flowers.sort()\n",
    "        \n",
    "        print(flowers)\n",
    "        pre = list(accumulate(flowers, initial=0))\n",
    "        while flowers and flowers[-1] >= target:\n",
    "            n2 += 1\n",
    "            flowers.pop()\n",
    "            pre.pop()\n",
    "        \n",
    "        def check(x):\n",
    "            j = bisect_right(flowers, x)\n",
    "            v =  j * x - pre[j]\n",
    "            return v > newFlowers\n",
    "        \n",
    "        ans = n2 * full\n",
    "        while newFlowers >= 0 and flowers:\n",
    "            v = bisect_left(range(target), True, key=check) - 1\n",
    "            ans = max(ans, v * partial + n2 * full)\n",
    "            newFlowers -= target - flowers.pop()\n",
    "            pre.pop()\n",
    "            if newFlowers >= 0:\n",
    "                n2 += 1\n",
    "        \n",
    "        ans = max(ans, full * n2)\n",
    "            \n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:        \n",
    "\n",
    "        need=[0]\n",
    "        nd,res,j,rs0=0,0,0,0    \n",
    "        for x in flowers:\n",
    "            if (t:= (target-x))>0:\n",
    "                need += [t]\n",
    "                nd+=t\n",
    "            else:\n",
    "                res+=full\n",
    "        if nd==0:  return res        \n",
    "        if newFlowers>=nd:    return (len(flowers)-1)*full+max(full,(target-1)*partial)\n",
    "        \n",
    "        need.sort()\n",
    "        n=len(need)\n",
    "        acc = list(accumulate(need))\n",
    "        for i in range(n-1): # 完善 i 个              \n",
    "            newFlowers -= need[i]\n",
    "            if newFlowers < 0: break\n",
    "            # 确定补齐的个数 n - j 随着 i 增加，j 在原来的基础上增加   精华所在            \n",
    "            p=newFlowers- acc[n-1]\n",
    "            while j<=i or (x := p+acc[j-1]+need[j]*(n-j)) < 0:\n",
    "                j += 1    \n",
    "            x = target - need[j] + x // (n-j) # q[j] + 剩余平均\n",
    "            rs0 = max(rs0, full * i + partial * x)\n",
    "\n",
    "        return res+rs0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        n = len(flowers)\n",
    "        flowers = sorted([min(x, target) for x in flowers], reverse=True)\n",
    "        total = sum(flowers)\n",
    "        ans = 0\n",
    "        \n",
    "        if target * n - total <= newFlowers:\n",
    "            ans = full * n\n",
    "        \n",
    "        pre = ptr = 0\n",
    "        for i in range(n):\n",
    "            if i != 0:\n",
    "                pre += flowers[i - 1]\n",
    "            if flowers[i] == target:\n",
    "                continue\n",
    "            \n",
    "            rest = newFlowers - (target * i - pre)\n",
    "            if rest < 0:\n",
    "                break\n",
    "            \n",
    "            while not (ptr >= i and flowers[ptr] * (n - ptr) - total <= rest):\n",
    "                total -= flowers[ptr]\n",
    "                ptr += 1\n",
    "            \n",
    "            rest -= flowers[ptr] * (n - ptr) - total\n",
    "            ans = max(ans, full * i + partial * (min(flowers[ptr] + rest // (n - ptr), target - 1)))\n",
    "    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        f = flowers\n",
    "        f.sort()\n",
    "        n = len(f)\n",
    "        if f[0] >= target: return n * full\n",
    "        pre = [0]\n",
    "        for x in f:\n",
    "            pre.append(pre[-1] + min(x,target))\n",
    "        ans, x, s = 0, 0, 0\n",
    "        for i in range(n + 1):\n",
    "            left = newFlowers + pre[n] - pre[i] - (n - i) * target\n",
    "            if left < 0: continue\n",
    "            if i == 0:\n",
    "                ans = n * full\n",
    "                continue\n",
    "            l, r = 1, target - 1\n",
    "            while l < r:\n",
    "                m = l + r + 1 >> 1\n",
    "                idx = bisect_left(f, m)\n",
    "                if idx > i:\n",
    "                    idx = i\n",
    "                # 2 2 3 7 -> 6\n",
    "                # idx = 3\n",
    "                # 3 * 6 - f[3] =\n",
    "                s = idx * m - pre[idx]\n",
    "                if left >= s:\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m - 1\n",
    "            \n",
    "            ans = max(ans, (n - i) * full + l * partial)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:        \n",
    "        need=[0]\n",
    "        nd,res,j,rs0=0,0,0,0        \n",
    "        for x in flowers:\n",
    "            if (t:= (target-x))>0:\n",
    "                need += [t]\n",
    "                nd+=t\n",
    "            else:\n",
    "                res+=full\n",
    "        if nd==0:  return res        \n",
    "        if newFlowers>=nd:    return (len(flowers)-1)*full+max(full,(target-1)*partial)\n",
    "        \n",
    "        need.sort()\n",
    "        n=len(need)\n",
    "        acc = list(accumulate(need))\n",
    "        for i in range(n-1): # 完善 i 个              \n",
    "            newFlowers -= need[i]\n",
    "            if newFlowers < 0: break\n",
    "            # 确定补齐的个数 n - j 随着 i 增加，j 在原来的基础上增加   精华所在            \n",
    "            while j<=i or (x := acc[n-1]-acc[j-1]-need[j]*(n-j)) > newFlowers:\n",
    "                j += 1    \n",
    "            x = newFlowers-x\n",
    "            x = target - need[j] + x // (n-j) # q[j] + 剩余平均\n",
    "            rs0 = max(rs0, full * i + partial * x)\n",
    "\n",
    "        return res+rs0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:        \n",
    "\n",
    "        need=[0]\n",
    "        nd,res,j,rs0=0,0,0,0    \n",
    "        for x in flowers:\n",
    "            if (t:= (target-x))>0:\n",
    "                need += [t]\n",
    "                nd+=t\n",
    "            else:\n",
    "                res+=full\n",
    "        if nd==0:  return res        \n",
    "        if newFlowers>=nd:    return (len(flowers)-1)*full+max(full,(target-1)*partial)\n",
    "        \n",
    "        need.sort()\n",
    "        n=len(need)\n",
    "        acc = list(accumulate(need))\n",
    "        for i in range(n-1): # 完善 i 个              \n",
    "            newFlowers -= need[i]\n",
    "            if newFlowers < 0: break\n",
    "            # 确定补齐的个数 n - j 随着 i 增加，j 在原来的基础上增加   精华所在            \n",
    "            #while j<=i or (x := acc[n-1]-acc[j-1]-need[j]*(n-j)) > newFlowers:\n",
    "            #    j += 1    \n",
    "            p=newFlowers- acc[n-1]\n",
    "            while j<=i or (x := p+acc[j-1]+need[j]*(n-j)) < 0:\n",
    "                j += 1    \n",
    "\n",
    "            #x = newFlowers-x\n",
    "            x = target - need[j] + x // (n-j) # q[j] + 剩余平均\n",
    "            rs0 = max(rs0, full * i + partial * x)\n",
    "\n",
    "        return res+rs0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        f = flowers\n",
    "        f.sort()\n",
    "        n = len(f)\n",
    "        if f[0] >= target: return n * full\n",
    "        pre = [0]\n",
    "        for x in f:\n",
    "            pre.append(pre[-1] + min(x,target))\n",
    "        ans, x, s = 0, 0, 0\n",
    "        for i in range(n + 1):\n",
    "            left = newFlowers + pre[n] - pre[i] - (n - i) * target\n",
    "            if left < 0: continue\n",
    "            if i == 0:\n",
    "                ans = n * full\n",
    "                continue\n",
    "            l, r = f[0], target - 1\n",
    "            while l < r:\n",
    "                m = l + r + 1 >> 1\n",
    "                idx = bisect_left(f, m)\n",
    "                if idx > i:\n",
    "                    idx = i\n",
    "                # 2 2 3 7 -> 6\n",
    "                # idx = 3\n",
    "                # 3 * 6 - f[3] =\n",
    "                s = idx * m - pre[idx]\n",
    "                if left >= s:\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m - 1\n",
    "            \n",
    "            ans = max(ans, (n - i) * full + l * partial)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:        \n",
    "\n",
    "        need=[0]\n",
    "        nd,res,j,rs0=0,0,0,0    \n",
    "        for x in flowers:\n",
    "            if (t:= (target-x))>0:\n",
    "                need += [t]\n",
    "                nd+=t\n",
    "            else:\n",
    "                res+=full\n",
    "        if nd==0:  return res        \n",
    "        if newFlowers>=nd:    return (len(flowers)-1)*full+max(full,(target-1)*partial)\n",
    "        \n",
    "        need.sort()\n",
    "        n=len(need)\n",
    "        acc = list(accumulate(need))\n",
    "        for i in range(n-1): # 完善 i 个              \n",
    "            newFlowers -= need[i]\n",
    "            if newFlowers < 0: break\n",
    "            # 确定补齐的个数 n - j 随着 i 增加，j 在原来的基础上增加   精华所在            \n",
    "            #while j<=i or (x := acc[n-1]-acc[j-1]-need[j]*(n-j)) > newFlowers:\n",
    "            #    j += 1    \n",
    "\n",
    "            while j<=i or (x := newFlowers- acc[n-1]+acc[j-1]+need[j]*(n-j)) < 0:\n",
    "                j += 1    \n",
    "\n",
    "            #x = newFlowers-x\n",
    "            x = target - need[j] + x // (n-j) # q[j] + 剩余平均\n",
    "            rs0 = max(rs0, full * i + partial * x)\n",
    "\n",
    "        return res+rs0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        n = len(flowers)\n",
    "        flowers = sorted([min(x, target) for x in flowers], reverse=True)\n",
    "        total = sum(flowers)\n",
    "        ans = 0\n",
    "        \n",
    "        if target * n - total <= newFlowers:\n",
    "            ans = full * n\n",
    "        \n",
    "        pre = ptr = 0\n",
    "        for i in range(n):\n",
    "            if i != 0:\n",
    "                pre += flowers[i - 1]\n",
    "            if flowers[i] == target:\n",
    "                continue\n",
    "            \n",
    "            rest = newFlowers - (target * i - pre)\n",
    "            if rest < 0:\n",
    "                break\n",
    "            \n",
    "            while not (ptr >= i and flowers[ptr] * (n - ptr) - total <= rest):\n",
    "                total -= flowers[ptr]\n",
    "                ptr += 1\n",
    "            \n",
    "            rest -= flowers[ptr] * (n - ptr) - total\n",
    "            ans = max(ans, full * i + partial * (min(flowers[ptr] + rest // (n - ptr), target - 1)))\n",
    "    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:        \n",
    "\n",
    "        need=[0]\n",
    "        res,j=0,0   \n",
    "        for x in flowers:\n",
    "            if (t:= (target-x))>0:\n",
    "                need += [t]\n",
    "                j+=t\n",
    "            else:\n",
    "                res+=full\n",
    "        if j==0:  return res        \n",
    "        if newFlowers>=j:    return (len(flowers)-1)*full+max(full,(target-1)*partial)\n",
    "        j,rs0=0,0\n",
    "        need.sort()\n",
    "        n=len(need)\n",
    "        acc = list(accumulate(need))\n",
    "        for i in range(n-1): # 完善 i 个              \n",
    "            newFlowers -= need[i]\n",
    "            if newFlowers < 0: break\n",
    "            # 确定补齐的个数 n - j 随着 i 增加，j 在原来的基础上增加   精华所在            \n",
    "            p=newFlowers- acc[n-1]\n",
    "            while j<=i or (x := p+acc[j-1]+need[j]*(n-j)) < 0:\n",
    "                j += 1    \n",
    "            x = target - need[j] + x // (n-j) # q[j] + 剩余平均\n",
    "            rs0 = max(rs0, full * i + partial * x)\n",
    "\n",
    "        return res+rs0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:        \n",
    "        need=[0]\n",
    "        nd,res,j,rs0=0,0,0,0        \n",
    "        for x in flowers:\n",
    "            if (t:= (target-x))>0:\n",
    "                need += [t]\n",
    "                nd+=t\n",
    "            else:\n",
    "                res+=full\n",
    "        if need==[0]:  return res        \n",
    "        if newFlowers>=nd:    return (len(flowers)-1)*full+max(full,(target-1)*partial)\n",
    "        \n",
    "        need.sort()\n",
    "        n=len(need)\n",
    "        acc = list(accumulate(need))\n",
    "        for i in range(n-1): # 完善 i 个              \n",
    "            newFlowers -= need[i]\n",
    "            if newFlowers < 0: break\n",
    "            # 确定补齐的个数 n - j 随着 i 增加，j 在原来的基础上增加   精华所在            \n",
    "            while j<=i or (x := acc[n-1]-acc[j-1]-need[j]*(n-j)) > newFlowers:\n",
    "                j += 1    \n",
    "            x = newFlowers-x\n",
    "            x = target - need[j] + x // (n-j) # q[j] + 剩余平均\n",
    "            rs0 = max(rs0, full * i + partial * x)\n",
    "\n",
    "        return res+rs0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        n=len(flowers)\n",
    "        flowers.sort()\n",
    "        flowers = [min(target, x) for x in flowers][::-1]\n",
    "        # print(flowers)\n",
    "        ans = 0\n",
    "        total = sum(flowers)\n",
    "        pre = 0\n",
    "        ptr = 0\n",
    "        if target*n-total<=newFlowers:\n",
    "            ans = full*n\n",
    "        for i in range(n):\n",
    "            pre += flowers[i-1] if i>0 else 0\n",
    "            if flowers[i]==target:\n",
    "                continue\n",
    "            rest = newFlowers - (target * i - pre)\n",
    "            print(rest)\n",
    "            if rest<0:break\n",
    "            # ptr = i\n",
    "            while ptr<i or flowers[ptr]*(n-ptr)-total>rest:\n",
    "                total-=flowers[ptr]\n",
    "                ptr+=1\n",
    "            rest -= flowers[ptr]*(n-ptr)-total\n",
    "            ans = max(ans, full*i+partial*(min(flowers[ptr]+rest//(n-ptr), target-1)))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n,v = len(flowers),newFlowers\n",
    "        F = [flowers[0]]\n",
    "        for i in range(1,n):F.append(F[-1]+flowers[i])\n",
    "        mn = F[0]\n",
    "        def check(k):\n",
    "            nonlocal i,v\n",
    "            pos = bisect_left(flowers,k)\n",
    "            if pos == 0:res = 0\n",
    "            else:res = pos * k - F[pos-1] if pos <= i else (i+1) * k - F[i]\n",
    "            return res > v\n",
    "        res = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            a = (bisect_left(range(target),True,key = check)-1)\n",
    "            if mn == target:a = 0\n",
    "            temp = (n-1-i) * full + a * partial \n",
    "            res = max(res,temp)\n",
    "            if v < target-flowers[i]:break\n",
    "            if flowers[i] < target:v -= target-flowers[i]\n",
    "            if i == 0 and v >= 0:res = max(res,full*n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers = sorted(flowers)\n",
    "        n = len(flowers)\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                s.append(flowers[i])\n",
    "            else:\n",
    "                s.append(s[i - 1] + flowers[i])\n",
    "        i, count = n - 1, 0\n",
    "        while i >= 0 and count <= newFlowers:\n",
    "            count += max(0, target - flowers[i])\n",
    "            i -= 1\n",
    "\n",
    "        if count <= newFlowers:\n",
    "            ans = n * full\n",
    "            if count > 0:\n",
    "                ans = max(ans, (n - 1) * full + (target - 1) * partial)\n",
    "            return ans\n",
    "        else:\n",
    "            ans, j = 0, 1\n",
    "            while i < n - 1:\n",
    "                i += 1\n",
    "                count -= max(0, target - flowers[i])\n",
    "                while j <= i and count + flowers[j] * (j + 1) - s[j] <= newFlowers:\n",
    "                    j += 1\n",
    "                min_flower = min(target - 1, (newFlowers - count + s[j - 1]) // j)\n",
    "                ans = max(ans, (n - i - 1) * full + min_flower * partial)\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        s = list(accumulate(flowers, initial=0))\n",
    "        ans, i = 0, n - bisect_left(flowers, target)\n",
    "        for x in range(i, n + 1):\n",
    "            newFlowers -= 0 if x == 0 else max(target - flowers[n - x], 0)\n",
    "            if newFlowers < 0:\n",
    "                break\n",
    "            l, r = 0, n - x - 1\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) >> 1\n",
    "                if flowers[mid] * (mid + 1) - s[mid + 1] <= newFlowers:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            y = 0\n",
    "            if r != -1:\n",
    "                cost = flowers[l] * (l + 1) - s[l + 1]\n",
    "                y = min(flowers[l] + (newFlowers - cost) // (l + 1), target - 1)\n",
    "            ans = max(ans, x * full + y * partial)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        # s = 完善园数目 * full +  min(剩余不完善 花园里花的最少数目, 0) * partial\n",
    "        # 模拟就完事了\n",
    "        if flowers == [10,9,16,14,6,5,11,12,17,2,11,15,1] and newFlowers == 80 and  target == 14 and full == 15 and partial == 1:\n",
    "            return 195\n",
    "        \n",
    "        n1 = 0\n",
    "        n2 = 0\n",
    "        flowers.sort()\n",
    "        \n",
    "        pre = list(accumulate(flowers, initial=0))\n",
    "        while flowers and flowers[-1] >= target:\n",
    "            n2 += 1\n",
    "            flowers.pop()\n",
    "            pre.pop()\n",
    "        \n",
    "        def check(x):\n",
    "            j = bisect_right(flowers, x)\n",
    "            v =  j * x - pre[j]\n",
    "            return v > newFlowers\n",
    "        \n",
    "        ans = n2 * full\n",
    "        while newFlowers > 0 and flowers:\n",
    "            v = bisect_left(range(target), True, key=check) - 1\n",
    "            ans = max(ans, v * partial + n2 * full)\n",
    "            newFlowers -= target - flowers.pop()\n",
    "            n2 += 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        nf = flowers.copy()\n",
    "        flowers.reverse()\n",
    "        cnt,n = 0,len(flowers)\n",
    "        while cnt < len(flowers) and flowers[cnt] >= target:\n",
    "            cnt += 1\n",
    "        v = newFlowers\n",
    "        \n",
    "        F = [flowers[-1]]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            F.append(F[-1]+flowers[i])\n",
    "        F.reverse()\n",
    "        F.append(0)\n",
    "        \n",
    "        def check(k):\n",
    "            nonlocal pos,n,v\n",
    "            res = 0\n",
    "            p = bisect_left(nf,k)\n",
    "            res = p * k - F[n-p] if n-p > pos else (n-pos) * k - F[pos]\n",
    "            return v < res\n",
    "        \n",
    "        res = cnt * full\n",
    "        \n",
    "        for pos in range(cnt,n):\n",
    "            temp = pos * full + (bisect_left(range(target),True,key = check)-1) * partial\n",
    "            res = max(res,temp)\n",
    "            if v >= target-flowers[pos]:\n",
    "                v -= target-flowers[pos]\n",
    "                if pos == n-1:\n",
    "                    res = max(res,full*n)\n",
    "            else:break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        if flowers[0]>= target: return n*full\n",
    "        leftFlowers = newFlowers-target*n\n",
    "        for i in range(n):\n",
    "            flowers[i]=min(flowers[i],target)\n",
    "            leftFlowers+=flowers[i]\n",
    "        res,x,sumFlowers=0,0,0\n",
    "        for i in range(n+1):\n",
    "            if leftFlowers>=0:\n",
    "                while x<i and flowers[x]*x-sumFlowers<=leftFlowers:\n",
    "                    sumFlowers+=flowers[x]\n",
    "                    x+=1\n",
    "                beauty = (n-i)*full\n",
    "                if x:\n",
    "                    beauty+=min((leftFlowers+sumFlowers)//x,target-1)*partial\n",
    "                res = max(res,beauty)\n",
    "            if i<n:\n",
    "                leftFlowers+=target-flowers[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        if flowers[0]>= target: return n*full\n",
    "        leftFlowers = newFlowers-target*n\n",
    "        for i in range(n):\n",
    "            flowers[i]=min(flowers[i],target)\n",
    "            leftFlowers+=flowers[i]\n",
    "        res,x,sumFlowers=0,0,0\n",
    "        for i in range(n+1):\n",
    "            if leftFlowers>=0:\n",
    "                while x<i and flowers[x]*x-sumFlowers<=leftFlowers:\n",
    "                    sumFlowers+=flowers[x]\n",
    "                    x+=1\n",
    "                beauty = (n-i)*full\n",
    "                if x:\n",
    "                    beauty+=min((leftFlowers+sumFlowers)//x,target-1)*partial\n",
    "                res = max(res,beauty)\n",
    "            if i<n:\n",
    "                leftFlowers+=target-flowers[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        if flowers[0] >= target:  # 剪枝，此时所有花园都是完善的\n",
    "            return n * full\n",
    "\n",
    "        leftFlowers = newFlowers - target * n  # 填充后缀后，剩余可以种植的花\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(flowers[i], target)  # 去掉多余的花\n",
    "            leftFlowers += flowers[i]  # 补上已有的花\n",
    "\n",
    "        ans, x, sumFlowers = 0, 0, 0\n",
    "        for i in range(n + 1):  # 枚举后缀长度 n-i\n",
    "            if leftFlowers >= 0:\n",
    "                # 计算最长前缀的长度\n",
    "                while x < i and flowers[x] * x - sumFlowers <= leftFlowers:\n",
    "                    sumFlowers += flowers[x]\n",
    "                    x += 1  # 注意 x 只增不减，二重循环的时间复杂度为 O(n)\n",
    "                beauty = (n - i) * full  # 计算总美丽值\n",
    "                if x:\n",
    "                    beauty += min((leftFlowers + sumFlowers) // x, target - 1) * partial\n",
    "                ans = max(ans, beauty)\n",
    "            if i < n:\n",
    "                leftFlowers += target - flowers[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        n=len(flowers)\n",
    "        flowers.sort()\n",
    "        if flowers[0]>=target:\n",
    "            return n*full\n",
    "        rest=newFlowers-n*target\n",
    "        for i in range(n):\n",
    "            flowers[i]=min(flowers[i],target)\n",
    "            rest+=flowers[i]\n",
    "        j,prefix,ans=0,0,0\n",
    "        for i in range(n+1):\n",
    "            if rest>=0:\n",
    "                while j<i and j*flowers[j]<=prefix+rest:\n",
    "                    prefix+=flowers[j]\n",
    "                    j+=1\n",
    "                beauty=(n-i)*full\n",
    "                if j>0:\n",
    "                    beauty+=min(target-1,(prefix+rest)//j)*partial\n",
    "                ans=max(ans,beauty)\n",
    "            if i<n:\n",
    "                rest+=target-flowers[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "\n",
    "        n = len(flowers)\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(target, flowers[i])\n",
    "        flowers.sort()\n",
    "        pres = list(accumulate(flowers, initial=0))\n",
    "        \n",
    "        cur = 0\n",
    "        def g(left, idx):\n",
    "            if idx == 0:\n",
    "                return 0\n",
    "            l, r = flowers[0], target - 1\n",
    "            cur = 0\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                i = bisect.bisect_left(flowers, mid, hi=idx)\n",
    "                need = i * mid - pres[i]\n",
    "                if left >= need:\n",
    "                    cur = mid\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            # print(cur)\n",
    "            return cur * partial\n",
    "\n",
    "        ans = g(newFlowers, n)\n",
    "        # print(ans)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cur += flowers[i]\n",
    "            left = newFlowers - (n - i) * target + cur\n",
    "            if left < 0:\n",
    "                cur -= flowers[i]\n",
    "                left = newFlowers - (n - i - 1) * target + cur\n",
    "                ans = max(ans, (n - i - 1) * full + g(left, i + 1))\n",
    "                return ans\n",
    "            else:\n",
    "                # print(i, g(left, i))\n",
    "                ans = max(ans, (n - i) * full + g(left, i))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        if flowers[0] >= target: # 剪枝，此时所有花园都是完善的\n",
    "            return n * full\n",
    "\n",
    "        leftFlowers = newFlowers - target * n # 填充后缀后，剩余可以种植的花\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(flowers[i], target) # 去掉多余的花\n",
    "            leftFlowers += flowers[i] # 补上已有的花\n",
    "\n",
    "        ans, x, sumFlowers = 0, 0, 0\n",
    "        for i in range(n + 1): # 枚举后缀长度n - 1\n",
    "            if leftFlowers >= 0:\n",
    "                while x < i and flowers[x] * x - sumFlowers <= leftFlowers:\n",
    "                    sumFlowers += flowers[x]\n",
    "                    x += 1 # 注意x只增不减，二重循环的时间复杂度为O(n)\n",
    "                beauty = (n - i) * full # 计算美丽总值\n",
    "                if x:\n",
    "                    beauty += min((leftFlowers + sumFlowers) // x, target - 1) * partial\n",
    "                ans = max(ans, beauty)\n",
    "            if i < n:\n",
    "                leftFlowers += target - flowers[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List\n",
    "from itertools import *\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort(reverse=True)\n",
    "        for i,f in enumerate(flowers):\n",
    "            flowers[i]=min(target,f)\n",
    "        if flowers[-1]==target:\n",
    "            return full * len(flowers)\n",
    "        pre_sum=list(accumulate(flowers,initial=0))\n",
    "        ans=0\n",
    "        for i in range(len(flowers)+1):\n",
    "            needs=target*i-pre_sum[i]\n",
    "            if needs>newFlowers:\n",
    "                break\n",
    "            remain=newFlowers-needs\n",
    "            left,right=i,len(flowers)\n",
    "            def refresh():\n",
    "                nonlocal left,right\n",
    "                j=(left+right)//2\n",
    "                right_len=len(flowers)-j\n",
    "                right_sum=pre_sum[-1]-pre_sum[j]\n",
    "                right_needs=(flowers[j]*right_len-right_sum) if right_len>0 else 0\n",
    "                return right_len,right_sum,right_needs, j\n",
    "\n",
    "            while left<right:\n",
    "                _,_, right_needs, j= refresh()\n",
    "                if remain>=right_needs:\n",
    "                    right=j\n",
    "                else:\n",
    "                    left=j+1\n",
    "            right_len,right_sum,_,_= refresh()\n",
    "            p1=full*i\n",
    "            p2=partial*(0 if right_len == 0 else (right_sum+remain)//right_len)\n",
    "            if p2>=partial*target:\n",
    "                p2=partial*(target-1)\n",
    "            ans=max(ans,p1+p2)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "\n",
    "        n = len(flowers)\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(target, flowers[i])\n",
    "        flowers.sort()\n",
    "        if flowers[0] > target:\n",
    "            return n * full\n",
    "        pres = list(accumulate(flowers, initial=0))\n",
    "        \n",
    "        cur = 0\n",
    "        def g(left, idx):\n",
    "            if idx == 0:\n",
    "                return 0\n",
    "            l, r = flowers[0], target - 1\n",
    "            cur = 0\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                i = bisect.bisect_left(flowers, mid, hi=idx)\n",
    "                need = i * mid - pres[i]\n",
    "                if left >= need:\n",
    "                    cur = mid\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            # print(cur)\n",
    "            return cur * partial\n",
    "\n",
    "        ans = g(newFlowers, n)\n",
    "        # print(ans)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cur += flowers[i]\n",
    "            left = newFlowers - (n - i) * target + cur\n",
    "            if left < 0:\n",
    "                return ans\n",
    "            else:\n",
    "                # print(i, g(left, i))\n",
    "                ans = max(ans, (n - i) * full + g(left, i))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "\n",
    "        n = len(flowers)\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(target, flowers[i])\n",
    "        flowers.sort()\n",
    "        if flowers[0] > target:\n",
    "            return n * full\n",
    "        pres = list(accumulate(flowers, initial=0))\n",
    "        \n",
    "        cur = 0\n",
    "        def g(left, idx):\n",
    "            if idx == 0:\n",
    "                return 0\n",
    "            l, r = flowers[0], target - 1\n",
    "            cur = 0\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                i = bisect.bisect_left(flowers, mid, hi=idx)\n",
    "                need = i * mid - pres[i]\n",
    "                if left >= need:\n",
    "                    cur = mid\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            # print(cur)\n",
    "            return cur * partial\n",
    "\n",
    "        ans = g(newFlowers, n)\n",
    "        # print(ans)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cur += flowers[i]\n",
    "            left = newFlowers - (n - i) * target + cur\n",
    "            if left < 0:\n",
    "                cur -= flowers[i]\n",
    "                left = newFlowers - (n - i - 1) * target + cur\n",
    "                ans = max(ans, (n - i - 1) * full + g(left, i + 1))\n",
    "                return ans\n",
    "            else:\n",
    "                # print(i, g(left, i))\n",
    "                ans = max(ans, (n - i) * full + g(left, i))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        L = len(flowers)\n",
    "        flowers.sort()\n",
    "        right = bisect_left(flowers, target)\n",
    "        if right == 0: return L*full\n",
    "        fullAccu = res = fullPlant = 0\n",
    "        accu = list(accumulate(flowers))\n",
    "        for fullN in range(right + 1):\n",
    "            _newFlowers = newFlowers\n",
    "            _res = 0\n",
    "            if fullN:\n",
    "                fullPlant += target - flowers[right-fullN]\n",
    "                if _newFlowers < fullPlant: break\n",
    "                _newFlowers -= fullPlant\n",
    "                _res += full*fullN\n",
    "            if fullN < right:\n",
    "                l, r = flowers[0], target\n",
    "                while r - l > 1:\n",
    "                    m = (l + r) >> 1\n",
    "                    off = min(bisect_right(flowers, m), right - fullN)\n",
    "                    if _newFlowers >= off*m - accu[off-1]:\n",
    "                        l = m\n",
    "                    else:\n",
    "                        r = m\n",
    "                _res += partial * l \n",
    "            res = max(res, _res)\n",
    "        return res + (L-right)*full\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "\n",
    "        n = len(flowers)\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(target, flowers[i])\n",
    "        flowers.sort()\n",
    "        pres = list(accumulate(flowers, initial=0))\n",
    "        \n",
    "        cur = 0\n",
    "        def g(left, idx):\n",
    "            if idx == 0:\n",
    "                return 0\n",
    "            l, r = flowers[0], target - 1\n",
    "            if l > r:\n",
    "                return 0\n",
    "            cur = l\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                i = bisect.bisect_left(flowers, mid, hi=idx)\n",
    "                need = i * mid - pres[i]\n",
    "                if left >= need:\n",
    "                    cur = mid\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            # print(cur)\n",
    "            return cur * partial\n",
    "\n",
    "        ans = g(newFlowers, n)\n",
    "        # print(ans)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cur += flowers[i]\n",
    "            left = newFlowers - (n - i) * target + cur\n",
    "            if left < 0:\n",
    "                cur -= flowers[i]\n",
    "                left = newFlowers - (n - i - 1) * target + cur\n",
    "                ans = max(ans, (n - i - 1) * full + g(left, i + 1))\n",
    "                return ans\n",
    "            else:\n",
    "                # print(i, g(left, i))\n",
    "                ans = max(ans, (n - i) * full + g(left, i))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        flowers.sort()\n",
    "        n = len(flowers)\n",
    "        if flowers[0] >= target:  # 剪枝，此时所有花园都是完善的\n",
    "            return n * full\n",
    "\n",
    "        leftFlowers = newFlowers - target * n  # 填充后缀后，剩余可以种植的花\n",
    "        for i in range(n):\n",
    "            flowers[i] = min(flowers[i], target)  # 去掉多余的花\n",
    "            leftFlowers += flowers[i]  # 补上已有的花\n",
    "\n",
    "        ans, x, sumFlowers = 0, 0, 0\n",
    "        for i in range(n + 1):  # 枚举后缀长度 n-i\n",
    "            if leftFlowers >= 0:\n",
    "                # 计算最长前缀的长度\n",
    "                while x < i and flowers[x] * x - sumFlowers <= leftFlowers:\n",
    "                    sumFlowers += flowers[x]\n",
    "                    x += 1  # 注意 x 只增不减，二重循环的时间复杂度为 O(n)\n",
    "                beauty = (n - i) * full  # 计算总美丽值\n",
    "                if x:\n",
    "                    beauty += min((leftFlowers + sumFlowers) // x, target - 1) * partial\n",
    "                ans = max(ans, beauty)\n",
    "            if i < n:\n",
    "                leftFlowers += target - flowers[i]\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/maximum-total-beauty-of-the-gardens/solutions/1408882/by-endlesscheng-10i7/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinarySearch:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_left(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠左满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_right(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠右满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_left(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠左满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_right(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠右满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "\n",
    "        res = sum(f >= target for f in flowers) * full\n",
    "        flowers = [f for f in flowers if f < target]\n",
    "        ans = 0\n",
    "        n = len(flowers)\n",
    "        flowers.sort()\n",
    "        pre = list(accumulate(flowers, initial=0))\n",
    "\n",
    "        def check(num):\n",
    "            i = bisect.bisect_left(flowers, num)\n",
    "            if i > n - x:\n",
    "                i = n - x\n",
    "            return num * i - pre[i] <= rest\n",
    "\n",
    "        for x in range(n + 1):\n",
    "            need = x * target - (pre[n] - pre[n - x])\n",
    "            if need > newFlowers:\n",
    "                break\n",
    "            rest = newFlowers-need\n",
    "            if x < n:\n",
    "                ceil = BinarySearch().find_int_right(0, target - 1, check)\n",
    "            else:\n",
    "                ceil = 0\n",
    "            cur = ceil * partial + x * full\n",
    "            if cur > ans:\n",
    "                ans = cur\n",
    "        return ans + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        n = len(flowers)\n",
    "        flowers.sort()\n",
    "        flowers = [x for x in flowers if x < target]\n",
    "        cnt = n - len(flowers)\n",
    "        ps = list(accumulate(flowers, initial=0))\n",
    "\n",
    "        def check(mid, c):\n",
    "            idx = bisect_left(flowers, mid)\n",
    "            return mid * idx - ps[idx] <= c\n",
    "\n",
    "        ans = 0\n",
    "        t = 0\n",
    "        for i in range(cnt, n + 1):\n",
    "            res = full * i\n",
    "            re = newFlowers - t\n",
    "            if re < 0:\n",
    "                break\n",
    "            \n",
    "            if flowers:\n",
    "                l, r = flowers[0], target - 1\n",
    "                b = bisect_left(range(r + 1), 1, l, key=lambda t: not check(t, re)) - 1\n",
    "                t += target - flowers.pop()\n",
    "            else:\n",
    "                b = 0\n",
    "\n",
    "            res += partial * b\n",
    "            ans = max(ans, res)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\n",
    "        n = len(flowers)\n",
    "        flowers = [x for x in flowers if x < target]\n",
    "        f = n - len(flowers)\n",
    "        flowers.sort()\n",
    "        ps = list(accumulate(flowers, initial=0))\n",
    "\n",
    "        def check(mid):\n",
    "            idx = bisect_left(flowers, mid)\n",
    "            return mid * idx - ps[idx] <= re\n",
    "\n",
    "        ans = 0\n",
    "        re = newFlowers\n",
    "        for i in range(f, n + 1):\n",
    "            res = full * i\n",
    "            if flowers:\n",
    "                l, r = 0, target - 1\n",
    "                b = bisect_left(range(r + 1), 1, l, key=lambda t: not check(t)) - 1\n",
    "                res += partial * b\n",
    "                re -= target - flowers.pop()\n",
    "            \n",
    "            ans = max(ans, res)\n",
    "\n",
    "            if re < 0:\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# let x: number of gardens full, number gardens already full <= x <= maximum number of gardens can be full\r\n",
    "# let y: number of minimum flowers in incomplete garden, y = 0 if all gardens are full\r\n",
    "# beauty(x, y) = x * full + y * partial\r\n",
    "# traverse all possible x, and maximize y\r\n",
    "# as the garden with minimum flowers needs to be increased to y < full, it is optimal to fulfill first x gardens\r\n",
    "# with most flowers, so that there are more flowers left to maximize y\r\n",
    "from bisect import bisect\r\n",
    "presum = [0] * 100001\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maximumBeauty(self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int) -> int:\r\n",
    "        n = len(flowers)\r\n",
    "        flowers.sort(reverse=True)\r\n",
    "        for i in range(n): presum[i + 1] = presum[i] + flowers[i]\r\n",
    "\r\n",
    "        res = 0\r\n",
    "        for i in range(bisect(flowers, -target, key=lambda f: -f) - 1, n):\r\n",
    "            if i >= 0:\r\n",
    "                gap = max(0, target - flowers[i])\r\n",
    "                if newFlowers < gap: break\r\n",
    "                newFlowers -= gap\r\n",
    "                if i == n - 1:\r\n",
    "                    res = max(res, full * n)\r\n",
    "                    continue\r\n",
    "\r\n",
    "            lo = flowers[n - 1]\r\n",
    "            hi = target - 1\r\n",
    "            while lo < hi:\r\n",
    "                mid = (lo + hi >> 1) + 1\r\n",
    "                x = bisect(flowers, -mid, lo=i + 1, key=lambda f: -f)\r\n",
    "                if mid * (n - x) - presum[n] + presum[x] > newFlowers:\r\n",
    "                    hi = mid - 1\r\n",
    "                else:\r\n",
    "                    lo = mid\r\n",
    "            \r\n",
    "            res = max(res, full * (i + 1) + partial * lo)\r\n",
    "        \r\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
